Hyntp: an Adaptive Hybrid Network Time Protocol for Clock Synchronization in Heterogeneous Distributed Systems

Background

Since the advent of asynchronous packet-based networks in communication and information technology, the topic of clock synchronization has received significant attention due to the temporal requirements of packet-based networks for the exchange of information. In more recent years, as distributed packet-based networks have evolved in terms of size, complexity, and, above all, application scope, there has been a growing need for new clock synchronization schemes with tractable design conditions to meet the demands of these evolving networks.

Distributed applications such as robotic swarms, automated manufacturing, and distributed optimization rely on precise time synchronization among distributed agents for their operation. For example, in the case of distributed control and estimation over networks, the uncertainties of packet-based network communication require timestamping of sensor and actuator messages in order to synchronize the information to the evolution of the dynamical system being controlled or estimated. Such a scenario is impossible without the existence of a common timescale among the non-collocated agents in the system. In fact, the lack of a shared timescale among the networked agents can result in performance degradation that can destabilize the system. Moreover, one cannot always assume that consensus on time is a given, especially when the network associated to the distributed system is subject to perturbations such as noise, delay, or jitter. Hence, it is essential that these networked systems utilize clock synchronization schemes that establish and maintain a common timescale for their algorithms.

With the arrival of more centralized protocols came motivated leader-less, consensus-based approaches by leveraging the seminal results on networked consensus in (e.g., Cao et al. 2008). More recent approaches (Garone et al. 2015, Kikuya et al. 2017) employ average consensus to give asymptotic results on clock synchronization under asynchronous and asymmetric communication topology. Unfortunately, a high number of iterations of the algorithm is often required before the desired synchronization accuracy is achieved. Furthermore, the constraint on asymmetric communication precludes any results guaranteeing stability or robustness. Lastly, these approaches suffer from over-complexity in term of both computation and memory allocation. Moreover, both synchronous and asynchronous scenarios require a large number of iterations before synchronization is achieved. Finally, the algorithm subjects the clocks to significant non-smooth adjustments in clock rate and offset that may prove undesirable in certain application settings.

Technology Description

To overcome these challenges, researchers at UC Santa Cruz (UCSC) have developed Hybrid Adaptive Hybrid Network Time Protocol (HyNTP), a distributed hybrid algorithm that synchronizes a set of clocks (e.g., connected over a heterogeneous network) to a common clock. HyNTP uses hybrid state-feedback to synchronize the clocks of the network agents and estimate the skew of its internal clock to allow for synchronization to a common timer rate. The protocol includes design conditions that guarantee synchronization of the timers such that they converge robustly, exponentially fast, even when information is available intermittently. The synchronous or asynchronous communication protocols are robust to noise in communication or hardware tolerances. In one or more examples, the term “hybrid” as used in “hybrid algorithm” or “hybrid feedback” defines the algorithm or feedback as using data that is: (1) updated at different event times, and (2) continuously evolved between the event times. Results from UCSC’s 2022 research demonstrated a strong performance of UCSC’s HyNTP algorithm in comparison to leading contemporary consensus-based clock synchronization algorithms, including PI-Consensus, RandSync, and Average TimeSync. Future work by UCSC may demonstrate the HyNTP’s robustness to a variety of perturbations and extend the problem to the case of asynchronous broadcasts between the nodes. Consideration will also be given to the scenario of time-varying clock skew parameters.

Applications

• Networking and related software
• Computers and related software
• IoT and related software

Features/Benefits

• HyNTP algorithm allows each agent to estimate skew of its internal clock in order to allow for synchronization to a common timer rate.
• HyNTP algorithm provides conditions that guarantee synchronization of the timers that are exponentially fast and robust as compared to leading contemporary consensus-based clock synchronization algorithms (2022)
• HyNTP’s synchronous or asynchronous communication methods are robust to noise in communication or hardware tolerances.

Intellectual Property Information

Related Materials

• Guarro, Marcello, and Ricardo G. Sanfelice. "HyNTP: A Distributed Hybrid Algorithm for Time Synchronization." arXiv preprint arXiv:2105.00165 (2021). - 05/01/2021